class Solution {
    int dp[10010] = { 0 };
    int pos = 0;
public:
    int LIS(vector<int>& a) {
        for (auto x : a)
        {
            if (pos == 0 || x > dp[pos])
            {
                dp[++pos] = x;
            }
            else
            {
                int left = 1, right = pos;
                while (left < right)
                {
                    int mid = (left + right) / 2;
                    if (dp[mid] >= x)
                        right = mid;
                    else
                        left = mid + 1;
                }

                dp[left] = x;
            }
        }

        return pos;
    }
};
